約 221,259 件
https://w.atwiki.jp/akitaicpc/pages/39.html
編集履歴 取得中です。 ...
https://w.atwiki.jp/akitaicpc/pages/37.html
ASCII コード アスキー(ASCII American Standard Code for Information Interchange)は英語圏などでよくつかわれる 文字コードです。 ICPCの問題では、Input,Outputともにアルファベットか数字、記号しか出てきません(つまり日本語はない) そのため、文字列処理を行うときに文字コードの番号を知りたい時があるかもしれないのでのせておきます。 初めの32文字(10進数で0-31)と最後の127(DEL 削除)は、ASCIIでは制御文字となっていて 残りの33-126は印刷可能文字です(32は空白文字) 編集上の都合により、文字 (不等号)と | (パイプ文字)と ~ (チルダ)は全角で表示していますが、 本当は半角なので気を付けてください。 制御文字 10進数 16進数 文字(Ctrl + ) 略文字(内容) 00 00 @ NUL(空文字) 01 01 A SOH(ヘッディング開始) 02 02 B STX(テキスト開始) 03 03 C ETX(テキスト終了) 04 04 D EOT(転送完了) 05 05 E ENQ(照会) 06 06 F ACK(受信完了) 07 07 G BEL(警報) 08 08 H BS(後退) 09 09 I HT(水平タブ) 10 0A J LF(改行) 11 0B K VT(垂直タブ) 12 0C L FF(改頁) 13 0D M CR(復帰) 14 0E N SO(シフトアウト) 15 0F O SI(シフトイン) 16 10 P DLE(データリンク拡張) 17 11 Q DC1(装置制御1) 18 12 R DC2(装置制御2) 19 13 S DC3(装置制御3) 20 14 T DC4(装置制御4) 21 15 U NAK(受信失敗) 22 16 V SYN(同期) 23 17 W ETB(転送ブロック終了) 24 18 X CAN(取り消し) 25 19 Y EM(メディア終了) 26 1A Z SUB(置換) 27 20 [ ESC(エスケープ) 28 21 \ FS(ファイル区切り) 29 22 ] GS(グループ区切り) 30 23 ^ RS(レコード区切り) 31 1F _ US(ユニット区切り) 127 7F DEL(削除) 印字可能文字 10進数 16進数 文字 32 20 (半角スペース) 33 21 ! 34 22 " 35 23 # 36 24 $ 37 25 % 38 26 39 27 40 28 ( 41 29 ) 42 2A * 43 2B + 44 2C , 45 2D - 46 2E . 47 2F / 48 30 0 49 31 1 50 32 2 51 33 3 52 34 4 53 35 5 54 36 6 55 37 7 56 38 8 57 39 9 58 3A 59 3B ; 60 3C 61 3D = 62 3E > 63 3F ? 64 40 @ 65 41 A 66 42 B 67 43 C 68 44 D 69 45 E 70 46 F 71 47 G 72 48 H 73 49 I 74 4A J 75 4B K 76 4C L 77 4D M 78 4E N 79 4F O 80 50 P 81 51 Q 82 52 R 83 53 S 84 54 T 85 55 U 86 56 V 87 57 W 88 58 X 89 59 Y 90 5A Z 91 5B [ 92 5C \ 93 5D ] 94 5E ^ 95 5F _ 96 60 ` 97 61 a 98 62 b 99 63 c 100 64 d 101 65 e 102 66 f 103 67 g 104 68 h 105 69 i 106 6A j 107 6B k 108 6C l 109 6D m 110 6E n 111 6F o 112 70 p 113 71 q 114 72 r 115 73 s 116 74 t 117 75 u 118 76 v 119 77 w 120 78 x 121 79 y 122 7A z 123 7B { 124 7C |(パイプ) 125 7D } 126 7E ~(チルダ) 備考 大文字のASCII値に32を加えると小文字に変換することが出来る。例えば char str = A ; str += 32; とすることで大文字のAが小文字のaに変換される。 この32というのは、 a - A で得られます。 また、数字から48減らすと数値を得られる。例えば char str = 1 ; str -= 48; if(str==1) printf("strの値は%dです",str); とすることで、変数strの値は文字 1 ではなく数値の1に変換されている (実行すると "strの値は1です" と出力される) この48というのは、 0 で得られます。余談ですが、数字の文字コードの下位4ビットは2進化10進数になっています。なので、 4 15 で4という数値を得ることができます。 ...
https://w.atwiki.jp/akitaicpc/pages/27.html
プログラミングコンテストで重要なアルゴリズム 基本的なアルゴリズム(最大値・最小値・素数判定・組み合わせ・順列など) 探索アルゴリズム(幅優先探索・深さ優先探索・枝刈り探索など) グラフアルゴリズム(ダイクストラ法・ベルマンフォード法・ワーシャルフロイド法・プリム法など) 動的計画法(DP) ソートアルゴリズム(挿入ソート・バブルソート・クイックソートなど) 計算幾何(線分の交差判定・円の当たり判定など) ...
https://w.atwiki.jp/akitaicpc/pages/2.html
サークル トップページ 2013年度日程 過去の結果 過去の活動の記録 メニュー トップページ ACM ICPCとは Linuxでよく使うコマンド ICPCの入出力について C++に関する情報 重要なアルゴリズム ICPCの過去問題 過去のコンテストの解説 その他・古典パズルなど 蟻本 競技プログラミングに役立つページ ライブラリ検証用問題 ICPC体験記など ページ一覧 編集履歴 練習用ページ リンク ACM-ICPC 公式 ACM-ICPC 2013(会津大会) ACM-ICPC 2012(東京大会) ACM-ICPC OB/OGの会 AIZU online judge PKU JudgeOnline AtCoder TopCoder部のカレンダー リンク一覧 ここを編集
https://w.atwiki.jp/akitaicpc/pages/66.html
ダイクストラ法 ダイクストラ法(Dijkstra s algorithm)とは,グラフ上の2点間の最短経路を 効率よく求めるアルゴリズムです。ただしエッジに負のコストがあると使えないアルゴリズムとなっています。 このページはグラフとはのページを見たことを前提に説明していますので、目を通してください。 このページではダイクストラ法をいかにしてC++でコーディングするかに注目するため、 ダイクストラ法のアルゴリズムの詳細は説明しません。下記のリンク先のページを見てください。 wikipedia ACM/ICPC国内予選突破の手引き グラフとはのページでグラフの情報を構造体として扱いましたが、 ダイクストラ法のためにメンバ変数を追加します。 struct Node{ vector int to;//どのノードとつながっているか vector int cost;//エッジのコスト //ここから下はダイクストラ法のために必要な情報 bool done;//確定ノードかどうか int minCost;//スタートノードからのコスト int from;//どのノードから来たか }; またエッジを追加する関数は //エッジを追加する関数 void addEdge(int v, int u, int weight, struct Node *node){ //ノードuはノードvとつながっている情報を入れる node[ u ].to.push_back( v ); //ノードuとノードvのエッジの重みを入れる node[ u ].cost.push_back( weight ); //有向グラフならここから下の処理が不要 //ノードvはノードuとつながっている情報を入れる node[ v ].to.push_back( u ); //ノードvとノードuのエッジの重みを入れる node[ v ].cost.push_back( weight ); } この関数はグラフとはのページと同じものです。 この関数を呼び出すことで必要なエッジを追加することができます。 ダイクストラ法のソースコード グラフの情報がすべて構造体nodeに入っている状態で 関数dijkstra()にノード数n、スタートノードの番号start、ゴールノードの番号end、構造体node, を渡すと最短経路を求めてくれます。 //ダイクストラ法 void dijkstra(int n, int start, int end, struct Node *node){ //変数の初期化 for(int i=0 ; i n ; i++){ node[i].done = false; node[i].minCost = -1; } node[start].minCost = 0;//スタートノードまでのコストは0 while(1){ int doneNode = -1;//最新の確定したノード番号(-1はNULLのかわり) for(int i=0 ; i n ; i++){ if( node[i].done==true ){//ノードiが確定しているときcontinue continue; } if( node[i].minCost 0 ){//ノードiまでの現時点での最小コストが不明のとき continue; } //確定したノード番号が-1かノードiの現時点の最小コストが小さいとき //確定ノード番号を更新する if( doneNode 0 || node[i].minCost node[doneNode].minCost){ doneNode = i; } } if(doneNode==-1) break;//すべてのノードが確定したら終了 node[doneNode].done = true;//ノードを確定させる for(int i=0 ; i node[doneNode].to.size() ; i++){ int to = node[doneNode].to[i]; int cost = node[doneNode].minCost + node[doneNode].cost[i]; //ノードtoはまだ訪れていないノード //またはノードtoへより小さいコストの経路だったら //ノードtoの最小コストを更新 if( node[to].minCost 0 || cost node[to].minCost ){ node[to].minCost = cost; node[to].from = doneNode; } } } } 最短経路を出力したい場合には vector int path;//最短経路の情報を保持するvector //最短経路をゴールから順にスタートまでたどる for(int i = end ; i != start ; i = node[i].from ){ path.push_back(i); } path.push_back(start); //最短経路の出力 cout "最短経路は" endl; for(int i = path.size()-1 ; i = 0 ; i--){ cout path[i] " "; } cout endl; 上の処理を関数dijkstra()を呼び出した後にmain関数に書くといいです。 最後に余分な空白文字がでるので気をつけてください。 最短距離を出力したい場合には cout node[end].minCost endl; と関数dijkstra()を呼び出した後にmain関数に書いてください。 まとめのソースコード -ダイクストラ法のソースプログラム /* *dijkstra.cpp *by otaks , 2010-06-20 */ #include iostream #include vector using namespace std; //ノードの数 #define NODE_NUM 10 struct Node{ vector int to;//どのノードとつながっているか vector int cost;//エッジのコスト //ここから下はダイクストラ法のために必要な情報 bool done;//確定ノードかどうか int minCost;//スタートノードからのコスト int from;//どのノードから来たか }; //エッジを追加する関数 void addEdge(int v, int u, int weight, struct Node *node){ //ノードuはノードvとつながっている情報を入れる node[ u ].to.push_back( v ); //ノードuとノードvのエッジの重みを入れる node[ u ].cost.push_back( weight ); //有向グラフならここから下の処理が不要 //ノードvはノードuとつながっている情報を入れる node[ v ].to.push_back( u ); //ノードvとノードuのエッジの重みを入れる node[ v ].cost.push_back( weight ); } // ダイクストラ法 void dijkstra(int n, int start, int end, struct Node *node){ //変数の初期化 for(int i=0 ; i n ; i++){ node[i].done = false; node[i].minCost = -1; } node[start].minCost = 0;//スタートノードまでのコストは0 while(1){ int doneNode = -1;//最新の確定したノード番号(-1はNULLのかわり) for(int i=0 ; i n ; i++){ if( node[i].done==true ){//ノードiが確定しているときcontinue continue; } if( node[i].minCost 0 ){//ノードiまでの現時点での最小コストが不明のとき continue; } //確定したノード番号が-1かノードiの現時点の最小コストが小さいとき //確定ノード番号を更新する if( doneNode 0 || node[i].minCost node[doneNode].minCost){ doneNode = i; } } if(doneNode==-1) break;//すべてのノードが確定したら終了 node[doneNode].done = true;//ノードを確定させる for(int i=0 ; i node[doneNode].to.size() ; i++){ int to = node[doneNode].to[i]; int cost = node[doneNode].minCost + node[doneNode].cost[i]; //ノードtoはまだ訪れていないノード //またはノードtoへより小さいコストの経路だったら //ノードtoの最小コストを更新 if( node[to].minCost 0 || cost node[to].minCost ){ node[to].minCost = cost; node[to].from = doneNode; } } } } int main(){ int n; while(1){ struct Node node[NODE_NUM]; cout "ノードの数を入力 "; cin n; if(n==0) break; for(int i=0 ; i n ; i++){ int m; cout "ノード番号" i "とつながっているノード数 "; cin m; for(int j=0 ; j m ; j++){ cout "ノード番号" i "とつながっているノード番号とコスト " endl; int cost,No; cin No cost; addEdge( i , No , cost , node); } } //ここまででグラフに関する情報(エッジ、ノード)は構造体node[]に入っている cout "スタートノード ゴールノード番号を入力 "; int start,end; cin start end; //ダイクストラ法で最短経路を求める dijkstra( n , start , end , node ); //最短経路を調べる vector int path;//最短経路の情報を保持するvector //最短経路をゴールから順にスタートまでたどる for(int i = end ; i != start ; i = node[i].from ){ path.push_back(i); } path.push_back(start); //最短経路の出力 cout "最短経路は" endl; for(int i = path.size()-1 ; i = 0 ; i--){ cout path[i] " "; } cout endl; //最短距離 cout node[end].minCost endl; } return 0; } 上のグラフに先ほどのダイクストラ法のプログラム(dijkstra.cpp)に適用してみます 初めにグラフの情報をいれます。 Input 5 1 1 1 2 0 1 2 2 3 1 2 3 6 4 3 2 2 6 4 1 2 2 3 3 1 上のInputを入力することで図のグラフの情報が構造体nodeにデータが入ります。 次にスタートノードとゴールノードの番号が聞かれているはずなので 0 3 と入力します Output 最短経路は 0 1 2 4 3 7 正しく最短経路と最短距離が出力されています。 なおこのプログラムはノード数入力のところで0を入力すると終了します。 あとは問題に応じてこのプログラムを書きかえてください。 ...
https://w.atwiki.jp/akitaicpc/pages/96.html
組合せ 組合せとは、いくつかの要素の集まりからいくつかの要素を選び出す方法です。 例えば、n個の要素{ a[0] , a[1] , a[2] , ... , a[n-1] }からk個選んだ組み合わせをすべて知りたいとするなら、 次のプログラムでnとkとa[0],a[1]...a[n-1]を入力すると組み合わせを漏れや重複なく出力してくれます。 #include iostream #include vector using namespace std; int first(int n){ return ((1 n) - 1); } int nextSet(int x){ int small, ripple, newSmall,ones; small = x -x; ripple = x + small; newSmall = ripple -ripple; ones = (( newSmall / small ) 1) - 1; return (ripple | ones); } vector int setComb(int s, int n){ vector int c; for(int i=0 ; i n ; i++){ if( s 1 ) c.push_back( a[i] ); s = 1; } return c; } int main(){ int n, k, x; vector int a, c; cin n k; for(int i=0 ; i n ; i++ ){ cin a[i]; } x = first(k); while( !(x ~first(n) ) ){ c = setComb( x , n ); for(int i=0 ; i c.size() ; i++){ cout c[i]; ( i == c.size()-1 )? cout endl cout ","; } x = nextSet( x ); } } ...
https://w.atwiki.jp/akitaicpc/pages/89.html
探索アルゴリズム 基本的な探索アルゴリズム 深さ優先探索 DFS? 幅優先探索 BFS? 二分探索? 枝刈り探索? ...
https://w.atwiki.jp/akitaicpc/pages/94.html
配列を逆順にする 配列を逆順にしたい時は、次のようにするとよいでしょう。( algorithm ヘッダをインクルードするのを忘れずに!) void reverseArray(int a[], int n){ for(int i=0 ; i n/2 ; i++) swap( a[i] , a[n-i-1] ); } 実はC++の algprithm ヘッダにはreverse()関数があるので文字列や配列などを逆順にする関数を自分で作る必要はありません。 例えばvector int vc;に対して逆順にしたいなら reverse( vc.begin() , vc.end() ); とするだけで逆順になります。 std stringも逆順にできるので文字列を逆順にするのも簡単です。 ...
https://w.atwiki.jp/akitaicpc/pages/40.html
エラトステネスのふるい(素数判定) 素数表を生成するアルゴリズムにエラトステネスのふるいというものがあります。 まずはこのアルゴリズムなしで素数かどうか調べる方法を考えてみます。 ある数が素数かどうか調べるにはその数がその数より小さい数すべて(1以外)で 割り切れない場合素数なのでfor文で回せば簡単にコーディングできそうです。 +プログラム例 /*入力した値が素数かどうか識別するプログラム*/ #include iostream using namespace std; int main(){ int n; while( cin n , n ){ bool flag = true; //1は素数でない if( n == 1 ) flag = false; //nを2から(n-1)まで割って割り切れるか調べる for (int i=2 ; i n ; i++ ){ if ( n % i == 0 ){ //割り切れたら素数でない flag = false; break; } } if( flag ) cout "数値は素数です" endl; else cout "数値は素数ではありません" endl; } } この方法では大きな数に対して素数判定をすると非常に時間がかかります。 エラトステネスのふるいという方法は先程よりも効率がよく10^6程度の数であれば高速に素数判定ができます。 wikidediaのエラトステネスの篩に詳しい説明があるのでここでは説明しません。 以下がプログラム例です。 /*1000000以下の素数で入力したn以下の素数をすべて出力するプログラム*/ #include iostream #include cmath const int MAX = 1000001; using namespace std; bool p[MAX]; void sieve_of_eratosthenes(){ for(int i=0 ; i MAX ; i++){ p[i] = (i =1)? false true ; } for(int i=2 ; i = sqrt(MAX)+1 ; i++){ if( p[i] ){ for(int j=i*2 ; j MAX ; j+=i){ p[j] = false; } } } } int main(){ int n; sieve_of_eratosthenes(); while( cin n , n ){ for(int i=n ; i 0 ; i--){ if( p[i] ){ cout i endl; } } } } ...
https://w.atwiki.jp/akitaicpc/pages/28.html
スタック・キュー (画像などを入れて解説してくれると助かります。私はうまいこと画像を用意できませんorz あと、読みづらいところ、間違ってるところあったらバッサリ書き換えちゃっていいですよ。) スタック スタック (stack) とはデータ構造の一つです。スタックにデータを追加することをプッシュ (push) と言い、スタックからデータを取り出すことをポップ (pop) と言います。後にプッシュしたデータほど先にポップされるという特徴があります。これを Last In, First Out (LIFO) といいます。 イメージとしては、筒を思い浮かべるとわかりやすいと思います。ここでいう筒とは、有限長の円柱や多角柱の一方の端に、その角柱の断面と同形状の壁がついているもののことをいいます。筒の開いている端から物を入れていくと、先に入れた物ほど後で取り出せ、後に入れた物ほど先に取り出せるのがわかると思います。 なお、スタックは C++ の STL ですでに実装されています。 STL のスタックを使うときは、 #include stack でクラステンプレートを読み込み、 std stack データ型 スタック変数名 で実際にスタックを使います。 プッシュは スタック変数名.push(データ) 一番上のデータを調べるときは スタック変数名.top() ポップは スタック変数名.pop() です。 キュー キュー (queue) もデータ構造の一つです。キューにデータを追加することをエンキュー (enqueue) と言い、キューからデータを取り出すことをデキュー (dequeue) と言います。先にエンキューしたデータほど先にデキューされるという特徴があります。これを First In, First Out (FIFO) と言います。 イメージとしては、レジの待ち行列を思い浮かべるとわかりやすいと思います。順番に並んでいて、先に並んだ人が先にレジのサービスを受けられるのがわかると思います。(横入りなどはないものとします) なお、キューは C++ の STL で実装されています。STL のキューを使うときは、 #include queue でクラステンプレートを読み込み。 std queue データ型 キュー変数名 で実際にキューを使います。 STL のキューはメソッド名がスタックと同じで、push でエンキュー、pop でデキューとなっています。 キュー変数名.push(データ)// エンキュー キュー変数名.pop()// デキュー また、先頭のデータ (デキューすると取り出されるデータ) を返すメソッドは front() で、末尾のデータ (直前にエンキューされたデータ) を返すメソッドは back() です。 キュー変数名.front()// 直前にエンキューされたデータ キュー変数名.back()// デキューすると取り出されるデータ ...